Count Complete Tree Nodes

发表于

Count Complete Tree Nodes

Question

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Anaylsis

LeetCode Discussion

普通的依次遍历每个节点返回总个数会TLE

由于题目要求查的是完全二叉树的节点个数，而完全二叉树只有最底层的叶子节点可以为空，存在的叶子节点都在最下层的左侧，利用该性质可以尽快得出总节点个数。

设一完全二叉树节点root的高度为h，判断右子树高度=h-1是否成立

  • 成立。root的左子树为一棵高度为h-1的完全二叉树。节点个数count=2^(h-1)+右子树节点个数
  • 不成立。root的右子树为一棵高度为h-2的完全二叉树。节点个数count=2^(h-2)+左子树节点个数

为了方便计算，height函数返回的树高度为1~n-1

I have O(log(n)) steps. Finding a height costs O(log(n)). So overall O(log(n)^2).

Code

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int countNodes(TreeNode root) {
    	return helper(root);
    }
  
  	private int helper(TreeNode root){
      	if(root==null)
          return 0;
      	return 1+helper(root.left)+helper(root.right);
  	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        int h=height(root);
        int cnt=0;
        while(root!=null){
            if(height(root.right)==h-1){        //Left child is a complete tree with h-1 height
                cnt+=1<<h;
                root=root.right;
            }else{
                cnt+=1<<h-1;
                root=root.left;
            }
            h--;
        }
        return cnt;
    }
    
    private int height(TreeNode root){
        return (root==null)?-1:height(root.left)+1;
    }
}